#include "string_array.h"
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
myStr::myStr(const char *a)
{
    length = 0;
    while (a[length]) length++;
    data=new char[length+2];
    next = new int[length + 2];
    nextVal = new int[length + 2];
    for (int i = 1; i <= length; i++) data[i] = a[i-1];
}
myStr::~myStr(){};

bool replaceStr(myStr& S, const int& start, const myStr& T, const myStr& V){
    if (start<1 || start+T.length>S.length)return 0;
    int i = start, j = 1;
    while (i <= S.length && j <= T.length)
    {
        if (S.data[i] == T.data[j]) { i++; j++; }
        else { i = i - j + 2; j = 1; }
    }
    if (j <= T.length)return 0;//匹配失败
    int index = i - T.length;
    if (index + V.length >= S.length)
    {
        char* p = new char[S.length + V.length + 5];
        for (int tem = 1; tem < index; tem++) p[tem] = S.data[tem];
        for (int k = 1; k <= V.length; k++) { p[index + k - 1] = V.data[k]; }
        for (int k = 0; *(S.data + index + T.length + k); k++) p[index + V.length + k] = S.data[index + T.length + k];
        S.data = p;
        S.length = S.length - T.length + V.length;
    }
    else
    {
        for (int k = 1; k <= V.length; k++) S.data[index + k - 1] = V.data[k];
    }//进行替换
    return 1;
}

void myStr::kmp_next()
{
    int i = 1; next[1] = 0; int j = 0;
    while (i < length)
    {
        if (j == 0 || data[i] == data[j])
        {
            i++; j++; next[i] = j;
        }
        else j = next[j];
    }
};

void myStr::kmp_nextVal()
{
    int i = 1; nextVal[1] = 0; int j = 0;
    while (i < length)
    {
        if (j == 0 || data[i] == data[j])
        {
            i++; j++;
            if (data[i] != data[j]) nextVal[i] = j;
            else nextVal[i] = nextVal[j];
        }
        else j = nextVal[j];
    }
};

int simpleMatch(const myStr &S, const myStr &T)
{

    int i = 1;
    int j = 1;
    while (i <= S.length && j <= T.length)
    {
        if (S.data[i] == T.data[j])
        {
            ++i;
            ++j;
        }
        else
        {
            i = i - j + 2;
            j = 1;
        }
    }
    if (j > T.length)
    {
        return i - T.length;
    }
    else
        return -1;
};

int kmpMatch(const myStr &S, const myStr &T)
{
    int i = 1, j = 1;//从1开始查找
    while (i <= S.length && j <= T.length)
    {
        if (j == 0 || S.data[i] == T.data[j]) { i++; j++; }
        else j = T.next[j];
    }
    if (j > T.length)return i - T.length;
    else return -1;
};

void myStr::print()
{
    for (int i = 1; i <= this->length; i++)
        cout << this->data[i];

    cout << endl;
}

void myStr::printNext()
{
    for (int i = 1; i <= length; i++)
        cout << next[i];
    cout << endl;
}

void myStr::printNextVal()
{
    for (int i = 1; i <= length; i++)
        cout << nextVal[i];
    cout << endl;
}

bool my_sort(matrixNode A, matrixNode B)
{
    if (A.row < B.row)
    {
        return true;
    }
    else if (A.row > B.row)
    {
        return false;
    }
    else
    {
        if (A.col < B.col)
        {
            return true;
        }
        else if (A.col >= B.col)
        {
            return false;
        }
    }
    return false;
}

myMatrix::myMatrix(const int &rNum, const int &cNum, const int &nNum, const int *data)
{
    rowNum = rNum;
    colNum = cNum;
    nodeNum = nNum;
    nodeList = (matrixNode *)malloc(nNum * sizeof(matrixNode));
    vector<matrixNode> sorted;
    for (int i = 0; i < nNum; i++)
    {
        sorted.push_back({data[3 * i], data[3 * i + 1], data[3 * i + 2]});
    }
    sort(sorted.begin(), sorted.end(), my_sort);
    for (int i = 0; i < sorted.size(); i++)
    {
        nodeList[i].row = sorted[i].row;
        nodeList[i].col = sorted[i].col;
        nodeList[i].value = sorted[i].value;
    }
    return;
};

myMatrix::~myMatrix()
{
    rowNum = 0;
    colNum = 0;
    nodeNum = 0;
    free(nodeList);
    nodeList = NULL;
    return;
};

myMatrix::myMatrix()
{
    nodeList = NULL;
    rowNum = 0;
    colNum = 0;
    nodeNum = 0;
    return;
};

myMatrix::myMatrix(const myMatrix &input)
{
    rowNum = input.rowNum;
    colNum = input.colNum;
    nodeNum = input.nodeNum;
    nodeList = (matrixNode *)malloc(nodeNum * sizeof(matrixNode));
    for (int i = 0; i < nodeNum; i++)
    {
        nodeList[i].row = input.nodeList[i].row;
        nodeList[i].col = input.nodeList[i].col;
        nodeList[i].value = input.nodeList[i].value;
    }
    return;
}

void myMatrix::copy(myMatrix &input)
{
    rowNum = input.rowNum;
    colNum = input.colNum;
    nodeNum = input.nodeNum;
    nodeList = (matrixNode *)malloc(nodeNum * sizeof(matrixNode));
    for (int i = 0; i < nodeNum; i++)
    {
        nodeList[i].row = input.nodeList[i].row;
        nodeList[i].col = input.nodeList[i].col;
        nodeList[i].value = input.nodeList[i].value;
    }
    return;
};

void myMatrix::FastTransposeSMatrix(myMatrix &T)
{
    T.rowNum = colNum;
    T.colNum = rowNum;
    T.nodeNum = nodeNum;
    T.nodeList = (matrixNode *)malloc(nodeNum * sizeof(matrixNode));
    if (nodeNum <= 0)
        return;
    int num[100001], cpot[100001];
    memset(num, 0, sizeof(num));
    memset(cpot, 0, sizeof(cpot));
    for (int i = 0; i < nodeNum; i++)
        num[nodeList[i].col]++;
    cpot[0] = 0;
    for (int i = 1; i < colNum; i++)
        cpot[i] = cpot[i - 1] + num[i - 1];
    int p = 0, q = 0;
    for (int i = 0; i < nodeNum; i++)
    {
        p = nodeList[i].col;
        q = cpot[p];
        T.nodeList[q].row = nodeList[i].col;
        T.nodeList[q].col = nodeList[i].row;
        T.nodeList[q].value = nodeList[i].value;
        cpot[p]++;
    }
}

void myMatrix::printMatrix()
{
    cout << rowNum << "," << colNum << "," << nodeNum << endl;

    for (int i = 0; i < nodeNum; i++)
        cout << nodeList[i].row << "," << nodeList[i].col << "," << nodeList[i].value << endl;
}
